package com.LatitudeYao;
import java.util.*;
/**
 * Created by GTS on 2017/8/2.
 */
class MyBinaryTree{
    int value;
    MyBinaryTree leftPointer;
    MyBinaryTree rightPointer;
    MyBinaryTree(int val){
         value = val;
    }
}
public class ReconstructBinaryTreeYM {
    public static void main(String[] args) {
        int[] preOrder ={1,2,4,7,3,5,6,8};
        int[] inOrder ={4,7,2,1,5,3,8,6};
        MyBinaryTree tree = reconstructBinaryTree(preOrder,inOrder);
    }

    public static MyBinaryTree reconstructBinaryTree(int[] pre,int[] in){

        if(pre==null ||in == null){//如果输入数组为空，则返回NULL
            return null;
        }
        int rootValue=pre[0];
        MyBinaryTree root=new MyBinaryTree(rootValue);//生成根节点
        root.leftPointer = root.rightPointer = null;
        if(pre.length==1) {
            if (in.length == 1 && pre[0] == in[0])//只有同一个节点，节点值相等
            {
                return root;
            }
            else{
                System.out.println("invalid input");
            }
        }
        int rootValueIndexInInOrder = 0;//中序遍历查找根节点，此处为索引值
        while(rootValueIndexInInOrder < in.length && in[rootValueIndexInInOrder]!= rootValue){
            rootValueIndexInInOrder++;
        }



        int[] leftSubTreePre = Arrays.copyOfRange(pre,1,rootValueIndexInInOrder+1);
        int[] leftSubTreeIn = Arrays.copyOfRange(in,0, rootValueIndexInInOrder);
        if(leftSubTreePre.length > 0){
            root.leftPointer = reconstructBinaryTree(leftSubTreePre,leftSubTreeIn);
        }
        int[] rightSubTreePre = Arrays.copyOfRange(pre,rootValueIndexInInOrder+1,pre.length);
        int[] rightSubTreeIn = Arrays.copyOfRange(in,rootValueIndexInInOrder+1,in.length);
        if(leftSubTreePre.length>0){
            root.rightPointer = reconstructBinaryTree(rightSubTreePre,rightSubTreeIn);
        }
        return root;
    }
}
